package leetCode.solution;

import java.util.HashMap;

public class MyLRU {
	static class Node<K, V> {
		K key;
		V value;
		Node<K, V> prev;
		Node<K, V> next;

		public Node() {
			super();
		}

		public Node(K key, V value) {
			super();
			this.key = key;
			this.value = value;
		}
	}

	public static void main(String[] args) {
		LRUChache<String, Integer> cache = new LRUChache<String, Integer>(3);
		cache.put("a", 1);
		cache.put("b", 2);
		cache.put("c", 2);
		cache.put("d", 4);
		System.out.println(cache.get("c"));
		System.out.println(cache.get("b"));
		cache.put("e", 5);
	}

	static class LRUChache<K, V> {
		int size;
		int capacity;
		Node<K, V> head;
		Node<K, V> tail;

		HashMap<K, Node> map = new HashMap<K, Node>();

		public LRUChache() {
			super();
		}

		public LRUChache(int capacity) {
			super();
			this.capacity = capacity;
		}

		public V get(K k) {
			if (!map.containsKey(k)) {
				return null;
			}
			Node node = map.get(k);
			moveToTail(node);
			return (V) node.value;
		}

		public Node<K, V> put(K k, V v) {
			Node res = null;
			if (!map.containsKey(k)) {
				if (this.size == this.capacity) {
					removeHead();
				}
				res = new Node(k, v);
				concatToTail(res);
				map.put(k, res);

			} else {
				res = map.get(k);
				res.value = v;
			}
			return res;
		}

		private void removeHead() {
			map.remove(this.head.key);
			Node newHead = this.head.next;
			if (this.size == 1) {
				this.head = null;
				this.tail = null;
			} else {
				this.head.next = null;
				newHead.prev = null;
				this.head = newHead;
			}
			this.size--;
		}

		private void moveToTail(Node node) {
			if (this.size == 1 || node.key == tail.key)
				return;
			if (node.key == head.key) {
				this.head = node.next;
			} else {
				node.prev.next = node.next;
			}
			node.next.prev = node.prev;
			this.tail.next = node;
			node.prev = this.tail;
			node.next = null;
			this.tail = node;
		}

		private void concatToTail(Node node) {
			if (this.tail == null) {
				this.head = node;
				this.tail = node;
			}
			this.tail.next = node;
			node.prev = this.tail;
			this.tail = node;
			this.size++;
		}
	}
}